package com.zhn;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 */
public class Permute {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] flag;
    public List<List<Integer>> permute(int[] nums) {
        flag = new boolean[nums.length];
        backTracking(nums);
        return res;
    }
    public void backTracking(int[] nums){
        //如果path和nums的长度相等，说明遍历到叶子节点，可以将当前结果路径添加到结果集中
        if(path.size() == nums.length)
            res.add(new ArrayList<>(path));
        for(int i = 0; i < nums.length; i++){
            //说明当前的数已经遍历过了
            if(flag[i]){
                continue;
            }
            path.add(nums[i]);
            //标记遍历过的元素，防止重复
            flag[i] = true;
            backTracking(nums);
            //回溯
            path.remove(path.size() - 1);
            //重新初始化，为了下次遍历
            flag[i] = false;
        }
    }
}
